//----------------------------------------------------------------------
//	File:			ANNperf.h
//	Programmer:		Sunil Arya and David Mount
//	Last modified:	03/04/98 (Release 0.1)
//	Description:	Include file for ANN performance stats
//
//	Some of the code for statistics gathering has been adapted
//	from the SmplStat.h package in the g++ library.
//----------------------------------------------------------------------
// Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
// David Mount.  All Rights Reserved.
//
// This software and related documentation is part of the Approximate
// Nearest Neighbor Library (ANN).  This software is provided under
// the provisions of the Lesser GNU Public License (LGPL).  See the
// file ../ReadMe.txt for further information.
//
// The University of Maryland (U.M.) and the authors make no
// representations about the suitability or fitness of this software for
// any purpose.  It is provided "as is" without express or implied
// warranty.
//----------------------------------------------------------------------
//      History:
//      Revision 0.1  03/04/98
//          Initial release
//      Revision 1.0  04/01/05
//          Added ANN_ prefix to avoid name conflicts.
//----------------------------------------------------------------------

#ifndef ANNperf_H
#define ANNperf_H

//----------------------------------------------------------------------
//	basic includes
//----------------------------------------------------------------------

#include <ANN/ANN.h> // basic ANN includes

//----------------------------------------------------------------------
// kd-tree stats object
//	This object is used for collecting information about a kd-tree
//	or bd-tree.
//----------------------------------------------------------------------

class ANNkdStats
{ // stats on kd-tree
public:
  int   dim;      // dimension of space
  int   n_pts;    // no. of points
  int   bkt_size; // bucket size
  int   n_lf;     // no. of leaves (including trivial)
  int   n_tl;     // no. of trivial leaves (no points)
  int   n_spl;    // no. of splitting nodes
  int   n_shr;    // no. of shrinking nodes (for bd-trees)
  int   depth;    // depth of tree
  float sum_ar;   // sum of leaf aspect ratios
  float avg_ar;   // average leaf aspect ratio
  //
  // reset stats
  void
  reset(int d = 0, int n = 0, int bs = 0)
  {
    dim = d;
    n_pts = n;
    bkt_size = bs;
    n_lf = n_tl = n_spl = n_shr = depth = 0;
    sum_ar = avg_ar = 0.0;
  }

  ANNkdStats() // basic constructor
  {
    reset();
  }

  void
  merge(const ANNkdStats & st); // merge stats from child
};

//----------------------------------------------------------------------
//  ANNsampStat
//	A sample stat collects numeric (double) samples and returns some
//	simple statistics.  Its main functions are:
//
//		reset()		Reset to no samples.
//		+= x		Include sample x.
//		samples()	Return number of samples.
//		mean()		Return mean of samples.
//		stdDev()	Return standard deviation
//		min()		Return minimum of samples.
//		max()		Return maximum of samples.
//----------------------------------------------------------------------
class ANNLIB_EXPORT ANNsampStat
{
  int    n;              // number of samples
  double sum;            // sum
  double sum2;           // sum of squares
  double minVal, maxVal; // min and max
public:
  void
  reset() // reset everything
  {
    n = 0;
    sum = sum2 = 0;
    minVal = ANN_DBL_MAX;
    maxVal = -ANN_DBL_MAX;
  }

  ANNsampStat() { reset(); } // constructor

  void
  operator+=(double x) // add sample
  {
    n++;
    sum += x;
    sum2 += x * x;
    if (x < minVal)
      minVal = x;
    if (x > maxVal)
      maxVal = x;
  }

  int
  samples()
  {
    return n;
  } // number of samples

  double
  mean()
  {
    return sum / n;
  } // mean

  // standard deviation
  double
  stdDev()
  {
    return sqrt((sum2 - (sum * sum) / n) / (n - 1));
  }

  double
  min()
  {
    return minVal;
  } // minimum
  double
  max()
  {
    return maxVal;
  } // maximum
};

//----------------------------------------------------------------------
//		Operation count updates
//----------------------------------------------------------------------

#ifdef ANN_PERF
#  define ANN_FLOP(n)                                                                                                  \
    {                                                                                                                  \
      ann_Nfloat_ops += (n);                                                                                           \
    }
#  define ANN_LEAF(n)                                                                                                  \
    {                                                                                                                  \
      ann_Nvisit_lfs += (n);                                                                                           \
    }
#  define ANN_SPL(n)                                                                                                   \
    {                                                                                                                  \
      ann_Nvisit_spl += (n);                                                                                           \
    }
#  define ANN_SHR(n)                                                                                                   \
    {                                                                                                                  \
      ann_Nvisit_shr += (n);                                                                                           \
    }
#  define ANN_PTS(n)                                                                                                   \
    {                                                                                                                  \
      ann_Nvisit_pts += (n);                                                                                           \
    }
#  define ANN_COORD(n)                                                                                                 \
    {                                                                                                                  \
      ann_Ncoord_hts += (n);                                                                                           \
    }
#else
#  define ANN_FLOP(n)
#  define ANN_LEAF(n)
#  define ANN_SPL(n)
#  define ANN_SHR(n)
#  define ANN_PTS(n)
#  define ANN_COORD(n)
#endif

//----------------------------------------------------------------------
//	Performance statistics
//	The following data and routines are used for computing performance
//	statistics for nearest neighbor searching.  Because these routines
//	can slow the code down, they can be activated and deactiviated by
//	defining the ANN_PERF variable, by compiling with the option:
//	-DANN_PERF
//----------------------------------------------------------------------

//----------------------------------------------------------------------
//	Global counters for performance measurement
//
//	visit_lfs	The number of leaf nodes visited in the
//				tree.
//
//	visit_spl	The number of splitting nodes visited in the
//				tree.
//
//	visit_shr	The number of shrinking nodes visited in the
//				tree.
//
//	visit_pts	The number of points visited in all the
//				leaf nodes visited. Equivalently, this
//				is the number of points for which distance
//				calculations are performed.
//
//	coord_hts	The number of times a coordinate of a
//				data point is accessed. This is generally
//				less than visit_pts*d if partial distance
//				calculation is used.  This count is low
//				in the sense that if a coordinate is hit
//				many times in the same routine we may
//				count it only once.
//
//	float_ops	The number of floating point operations.
//				This includes all operations in the heap
//				as well as distance calculations to boxes.
//
//	average_err	The average error of each query (the
//				error of the reported point to the true
//				nearest neighbor).  For k nearest neighbors
//				the error is computed k times.
//
//	rank_err	The rank error of each query (the difference
//				in the rank of the reported point and its
//				true rank).
//
//	data_pts	The number of data points.  This is not
//				a counter, but used in stats computation.
//----------------------------------------------------------------------

extern int         ann_Ndata_pts;  // number of data points
extern int         ann_Nvisit_lfs; // number of leaf nodes visited
extern int         ann_Nvisit_spl; // number of splitting nodes visited
extern int         ann_Nvisit_shr; // number of shrinking nodes visited
extern int         ann_Nvisit_pts; // visited points for one query
extern int         ann_Ncoord_hts; // coordinate hits for one query
extern int         ann_Nfloat_ops; // floating ops for one query
extern ANNsampStat ann_visit_lfs;  // stats on leaf nodes visits
extern ANNsampStat ann_visit_spl;  // stats on splitting nodes visits
extern ANNsampStat ann_visit_shr;  // stats on shrinking nodes visits
extern ANNsampStat ann_visit_nds;  // stats on total nodes visits
extern ANNsampStat ann_visit_pts;  // stats on points visited
extern ANNsampStat ann_coord_hts;  // stats on coordinate hits
extern ANNsampStat ann_float_ops;  // stats on floating ops
//----------------------------------------------------------------------
//  The following need to be part of the public interface, because
//  they are accessed outside the DLL in ann_test.cpp.
//----------------------------------------------------------------------
ANNLIB_EXPORT extern ANNsampStat ann_average_err; // average error
ANNLIB_EXPORT extern ANNsampStat ann_rank_err;    // rank error

//----------------------------------------------------------------------
//	Declaration of externally accessible routines for statistics
//----------------------------------------------------------------------

ANNLIB_EXPORT void
annResetStats(int data_size); // reset stats for a set of queries

ANNLIB_EXPORT void
annResetCounts(); // reset counts for one queries

ANNLIB_EXPORT void
annUpdateStats(); // update stats with current counts

ANNLIB_EXPORT void
annPrintStats(ANNbool validate); // print statistics for a run

#endif
